def insertion_sort(nums: list[int]):
    """插入排序"""  # 升序：把当前遍历值“插入”到左边已排好序列的合适位置
    
    n = len(nums)
    for i in range(1, n):  # 外循环：左 [1, n-1] 右
        base = nums[i]  # 记录当前遍历值
        j = i - 1
        while j >= 0 and nums[j] > base:  # 内循环：右 [i-1, 合适位置] 左
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = base


if __name__ == "__main__":
    nums = [4, 1, 3, 1, 5, 2]
    insertion_sort(nums)
    print("排序完成后 nums =", nums)
    # 排序完成后 nums = [1, 1, 2, 3, 4, 5]
